package com.jxb.test20241216;

import java.util.Arrays;

public class Sort10 {

    public static void main(String[] args) {
        int[] nums = {5,2,3,1,4,5,6,7,4,2,4,5,2,3,6,7,3,4,6,7,8,9,0,4,5,6,7,8,9,0,5,5};
        System.out.println("排序开始----------------->" + Arrays.toString(nums));
        int[] res = sortArray(nums);
        System.out.println("排序结束----------------->" + Arrays.toString(res));
    }

    public static int[] sortArray(int[] nums) {
        if (nums.length <= 0) {
            return nums;
        }
        return sort(nums,0,nums.length - 1);
    }

    private static int[] sort(int[] nums, int start, int end) {
        //将数据分割成2部分，获取分区指示器
        int zoneIndex = partition(nums,start,end);
        if (zoneIndex > start) {
            sort(nums,start,zoneIndex-1);
        }
        if (zoneIndex < end) {
            sort(nums,zoneIndex+1,end);
        }
        return nums;
    }

    public static int partition(int[] array, int start, int end) {
        if (start == end) {
            return start;
        }
        //选择一个基数，数组的最后一位
        int basicNum = array[end];
        //设置分区指示器
        int zoneIndex = start - 1;
        for (int i = start;i<=end;i++) {
            if (array[i] <= basicNum) {
                zoneIndex++;
                //当前元素再分区指示器的右边时，交换当前元素和分区指示器元素
                if (i > zoneIndex) {
                    int temp = array[i];
                    array[i] = array[zoneIndex];
                    array[zoneIndex] = temp;
                }
            }
        }
        return zoneIndex;
    }

}
